{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Symmetric k-ary Tree（镜像多叉树）\n",
    "\n",
    "[@mjd507][1] | [Wechat Channel（微信公众号）][2]\n",
    "\n",
    "![Logo](images/Day75-1.png)\n",
    "\n",
    "[1]: https://github.com/mjd507\n",
    "[2]: https://mp.weixin.qq.com/s/xDqHfUupLDPB5d_4jECuNQ"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A *k-ary tree* is a tree with k-children, and a tree is *symmetrical* if the data of the left side of the tree is the same as the right side of the tree.\n",
    "\n",
    "```text\n",
    "#            4\n",
    "#          /   \\\n",
    "#        3       3\n",
    "#      / | \\   / | \\\n",
    "#     9  4  1 1  4  9\n",
    "```\n",
    "\n",
    "Given a k-ary tree, figure out if the tree is symmetrical."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "一棵*k叉树*是一棵拥有k个孩子的树，当一棵树的左侧与右侧相同时，这棵树是*镜像的*。\n",
    "\n",
    "给定一棵k叉树，判断它是否为镜像树。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Starting Point（初始模板）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node(object):\n",
    "    ''' The definition of a node '''\n",
    "\n",
    "    def __init__(self, value: int, children: list =[]):\n",
    "        ''' The constructor '''\n",
    "        self.value = value\n",
    "        self.children = children"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_symmetric(root: Node) -> bool:\n",
    "    ''' Recursively Algorithm '''\n",
    "    def helper(tree_A: Node, tree_B: Node) -> bool:\n",
    "        # Both trees are None.\n",
    "        if not tree_A and not tree_B:\n",
    "            return True\n",
    "        # Only one of them exists.\n",
    "        elif not (tree_A and tree_B):\n",
    "            return False\n",
    "        # The root of their value aren't the same.\n",
    "        elif tree_A.value != tree_B.value:\n",
    "            return False\n",
    "        # They both have no children.\n",
    "        elif not tree_A.children and not tree_B.children:\n",
    "            return True\n",
    "        # Only one of them has children.\n",
    "        elif not tree_A.children or not tree_B.children:\n",
    "            return False\n",
    "        # They have different amount of children.\n",
    "        elif len(tree_A.children) != len(tree_B.children):\n",
    "            return False\n",
    "        # Count their children.\n",
    "        length = len(tree_A.children)\n",
    "        # Traverse their children in the opposite way, and ...\n",
    "        for i in range(length):\n",
    "            # Check recursively.\n",
    "            result = helper(\n",
    "                tree_A.children[i],\n",
    "                tree_B.children[length - 1 - i]\n",
    "            )\n",
    "            if not result:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    return helper(tree, tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases（测试用例）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = Node(4)\n",
    "tree.children = [Node(3), Node(3)]\n",
    "tree.children[0].children = [Node(9), Node(4), Node(1)]\n",
    "tree.children[1].children = [Node(1), Node(4), Node(9)]\n",
    "is_symmetric(tree)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
